package person.bing.fbcloud.leetcode;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;

/**
 * @author: mengfanbing
 * @date: 2020/7/29 10:08
 */
public class Q5 {

    public static void main(String[] args) {
        String s = "ababa";
        String s1 = longestPalindrome(s);
        System.out.println(s1);
    }



    //中心扩散
    public static String longestPalindrome(String s) {
        String ans = "";
        int length = s.length();
        for (int i=0;i<length;i++){
            ans = getSubStringByMiddle(s,length,i,i,ans);
            ans = getSubStringByMiddle(s,length,i,i+1,ans);
        }
        return ans;
    }
    public static String getSubStringByMiddle(String s,int length,int a,int b,String ans){
        while (a>=0 && b<length && s.substring(a,a+1).equals(s.substring(b,b+1))){
            a--;
            b++;
        }
        String substring = s.substring(a + 1, b);
        if (substring.length() > ans.length()){
            ans = substring;
        }
        return ans;
    }

    //1.暴力解法
    //遍历每个字串，判断是否回文
    //回文并且比记录的回文子串长，则替换
    public static String longestPalindrome3(String s) {
        String ans = "";
        int length = s.length();
        for (int i=0;i<length;i++){
            for (int j=i+1;j<length+1;j++){
                String substring = s.substring(i, j);
                boolean palindrome = isPalindrome(substring);
                if (palindrome && substring.length() > ans.length()){
                    ans = substring;
                }
            }
        }
        return ans;
    }
    public static boolean isPalindrome(String s) {
        int length = s.length();
        int i = 0;
        int j = length-1;
        while (i<j){
            if (false == (s.substring(i,i+1).equals(s.substring(j,j+1)))){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }



    //超时
    public static String longestPalindrome2(String s) {
        if(s == null){
            return null;
        }
        if(s.length()==0){
            return "";
        }
        int length = 1;
        String ans = s.substring(0,1);
        int sLength = s.length();
        char[] chars = s.toCharArray();
        for (int i=sLength-1;i>0;i--){
            int start = 0;
            while (true){
                int iIndex = s.indexOf(chars[i],start);
                int subLength = i - iIndex + 1;
                if (subLength>1 && subLength>length){
                    start++;
                    String substring = s.substring(iIndex, i+1);
                    char[] subChars = substring.toCharArray();
                    int a = 0;
                    int b = subLength-1;
                    while (a<b){
                        if (subChars[a] == subChars[b]){
                            a++;
                            b--;
                        }else {
                            break;
                        }
                    }
                    if (a>=b){
                        length = subLength;
                        ans = substring;
                    }
                    continue;
                }else {
                    break;
                }
            }
        }
        return ans;
    }




    private enum Q5Enum{
        SPRING,
        SUMMER,
        WINTER,
        ;
    }
}
